1. Field of the Invention
The present invention relates to a filtering apparatus, a filtering method, a program, and a surround processor. In particular, the invention relates to a filtering apparatus in which a convolution computation of a discrete-time signal and a filter coefficient is performed through a multiplication in a frequency domain by using fast Fourier transform, and the like.
2. Description of the Related Art
A consideration will be considered on a method of obtaining an output in a case where a discrete-time signal having a length of N (N is an integer) is input to an FIR (Finite impulse Response) filter with a filter coefficient having a length of M (M is an integer). The FIR filter is a filter whose duration time of an impulse response is finite. A discrete-time signal having a length of N is set as x[n] (n=0, 1, 2, . . . , N−1), and a filter coefficient having a length of M is set as h[m] (m=0, 1, 2, . . . , M−1), and an output is set as y[n] (n=0, 1, 2, . . . , N−1). Here, x[n] and h[m] are real numbers, and N≧M−1 is satisfied.
An output y[n] in a case where the discrete-time signal x[n] is input to the FIR filter with the filter coefficient of h[m] can be obtained as shown in an expression (1) through a convolution computation in a time domain. Hereinafter, the convolution computation in the time domain is referred to as the “method A”.
                              y          ⁡                      [            n            ]                          =                              ∑                          m              =              0                                      M              -              1                                ⁢                                    h              ⁡                              [                m                ]                                      ⋆                          x              ⁡                              [                                  n                  -                  m                                ]                                                                        (        1        )            
In addition to the “method A”, a method of attaining the equivalence as the “method A” by obtaining DFTs (Discrete Fourier transform) of x[n] and h[m], multiplying these, and performing IDFT (Inverse Discrete Fourier transform) is also proposed.
The DFTs at N points of x[n] and h[m] are respectively set as X[k] and H[k] where k=0, 1, 2, . . . , N−1. A result of obtaining the DFTs at the N points of x[n] and h[m] and performing the multiplication is set as Y′[k]. In this case, Y′[k] is represented by an expression (2).Y′[k]=X[k]*H[k]  (2)
Where, when the IDFT at the N points of Y′[k] is set as y′[n], on the basis of the cyclic convolution theorem, y′[n] is represented by an expression (3).
                                          y            ′                    ⁡                      [            n            ]                          =                              ∑                          m              =              0                                      M              -              1                                ⁢                                    h              ⁡                              [                m                ]                                      ⋆                                          x                ⁡                                  [                                      n                    -                    m                                    ]                                            ⁢              N                                                          (        3        )            
Where, x[n−m]N is obtained by cyclically shifting x[n] to the right by m. That is, although x[n] and [m] are multiplied in the frequency domain by using the DFT, an inverse DFT is a convolution computation of a signal obtained by cyclically shifting x[n] to the right by m in the time domain and h[m], and therefore y[n] and y′[n] do not have equivalence.
In view of the above, a method is proposed of attaining equivalence between the result y′[n] obtained by padding (M−1) pieces of zero after x[n], performing the multiplication in the frequency domain, and performing the IDFT and the convolution computation result y[n] in the time domain (for example, see Alan V. Oppenheim, Ronald W. Schafer: “DISCRETE-TIME SIGNAL PROCESSING”, PRENTICLE HALL, pp. 548-560). That is, by performing such a zero padding processing, the convolution computation in the time domain can be replaced by the multiplication in the frequency domain.
Here, for reducing calculation costs, FFT (fast Fourier transform) is used instead of DFT. In this case, prior to the FFT processing, data length is set to have a multiplier of 2. The phrase “multiplier of 2,” as used throughout the specification and in the claims, is intended to convey the same meaning as “power of 2” as commonly understood in the art to indicate FFT data length. In a case where the FFT is used to realize an equivalent computation to the convolution computation in the time domain through multiplication in the frequency domain, while taking into account a restraint by the cyclic convolution theorem and a restraint for performing the FFT, a computation is performed in such a manner that at least (M−1) pieces of zero are padded after x[n], and the length (transform length) of is set to have a multiplier of 2.
The method of performing such a processing and using the FFT to realize the convolution through multiplication in the frequency domain is referred to as the “method B”. As N and M are larger, the “method B” is more superior to the “method A” in terms of computation amount.
FIG. 13 shows a configuration example of a filtering apparatus 200 in which the convolution computation of x[n] and [m] is performed through the “method B” while the transform length is set as L (L is a multiplier of 2). The filtering apparatus 200 includes a zero padding unit 201, a fast Fourier transform unit 202, a zero padding unit 203, a fast Fourier transform unit 204, a multiplication unit 205, and an inverse fast Fourier transform unit 206.
The zero padding unit 201 obtains zero padded data x′[n] (0≦n≦L−1) by padding (L−N) pieces of zero after the discrete-time signal x[n] having the length of N (0≦n≦N−1). The fast Fourier transform unit 202 performs the FFT (fast Fourier transform) on the zero padded data x′[n] obtained by the zero padding unit 201 to obtain frequency domain data X[k] (0≦k≦L−1).
The zero padding unit 203 obtains zero padded data h′[n] (0≦n≦L−1) by padding (L−M) pieces of zero after a filter coefficient h[m] having a length of M (0≦m≦M−1). The fast Fourier transform unit 204 performs the FFT (fast Fourier transform) on the zero padded data h′[n] obtained by the zero padding unit 203 to obtain frequency domain data H[k] (0≦k≦L−1).
The multiplication unit 205 multiplies the frequency domain data X[k] obtained by the fast Fourier transform unit 202 by the frequency domain data H[k] obtained by the fast Fourier transform unit 204 to obtain a multiplication result Y[k] (0≦k≦L−1). Then, the inverse fast Fourier transform unit 206 performs the IFFT (inverse fast Fourier transform) on the multiplication result Y[k] obtained by the multiplication unit 205 to obtain an output discrete-time signal y[n] (0≦n≦L−1).
An operation of the filtering apparatus 200 of FIG. 13 will be described. The filtering target discrete-time signal x[n] having the length of N is supplied to the zero padding unit 201. In the zero padding unit 201, (L−N) pieces of zero are padded after the discrete-time signal x[n] having the length of N, and the zero padded data x′[n] having a length (transform length) of L is obtained. The zero padded data x′[n] is supplied to the fast Fourier transform unit 202. In the fast Fourier transform unit 202, the FFT (fast Fourier transform) is performed on the zero padded data x′[n] to obtain the frequency domain data X[k] (0≦k≦L−1).
Also, the filter coefficient h[m] having the length of M is supplied to the zero padding unit 203. In the zero padding unit 203, (L−M) pieces of zero are padded after the filter coefficient h[m] having the length of M, and the zero padded data h′[n] having a length (transform length) of L is obtained. The zero padded data h′[n] is supplied to the fast Fourier transform unit 204. In the fast Fourier transform unit 204, the FFT (fast Fourier transform) is performed on the zero padded data h′[n], and the frequency domain data H[k] is obtained.
The frequency domain data X[k] obtained by the fast Fourier transform unit 202 and the frequency domain data H[k] obtained by the fast Fourier transform unit 204 are supplied to the multiplication unit 205. In the multiplication unit 205, the frequency domain data X[k] is multiplied by the frequency domain data H[k], and the multiplication result Y[k] is obtained. The multiplication result Y[k] is supplied to the inverse fast Fourier transform unit 206. In the inverse fast Fourier transform unit 206, the IFFT (inverse fast Fourier transform) is performed on the multiplication result Y[k], and the output discrete-time signal y[n] is obtained.